import java.util.ArrayList;


public class Ex6_5_beta {

	/**
	 * PLEASANTLY
	   -ME--AN-LY
	   https://class.coursera.org/bioinformatics-001/forum/thread?thread_id=768
	 */
	public Ex6_5_beta() {
		resultV = "";
		resultW = "";
	}

	public String resultV, resultW;
	public 	int back[][];

	public static void main(String[] args) {
		Ex6_5_beta exer = new Ex6_5_beta();
		ArrayList<String> inputs = Utils.readLines("C:\\Users\\josemfer\\Downloads\\dataset_79_14.txt");
		//ArrayList<String> inputs = Utils.readLines("C:\\Users\\josemfer\\Downloads\\input_6_5.txt");
		String v = inputs.get(0);
		String w = inputs.get(1);			
		int[][] scores = exer.getScores(v, w);
		int finalScore = scores[v.length()][w.length()];
		exer.getOutputLCS(exer.back,v,w,v.length(),w.length());
		Utils.writeFile( finalScore + "\r\n" 
				+ exer.resultV + "\r\n" 
				+ exer.resultW, 
				"C:\\Users\\josemfer\\Downloads\\out_7_6.txt");
		System.out.println(finalScore);
		System.out.println(exer.resultV);
		System.out.println(exer.resultW);
		
		

	}


	private void getOutputLCS(int[][] backtrack, 
			String v, String w, int i, int j) {
		//System.out.println("i=" + i + "   j=" + j);
		if (i == 0 && j == 0) {
			return;
		}
		if (backtrack[i][j] == 2 ) { // '0' = down
			getOutputLCS(backtrack,v,w,i-1,j);			
			resultV += v.charAt(i -1);
			resultW += "-";

		} else if (backtrack[i][j] == 0) {   // '1' = right 
			getOutputLCS(backtrack,v,w,i,j -1);
			resultV += "-";
			resultW += w.charAt(j-1);

		} else if (backtrack[i][j] == 1) {
			getOutputLCS(backtrack,v,w,i-1,j-1);   //  '2' = diagonal
			resultV += v.charAt(i-1);
			resultW += w.charAt(j-1);			
		}		
	}	

	/*
	 *   '0' = down   '1' = right   '2' = diagonal
	 */
	private int[][] getScores(String v, String w) {				
		int sigma = 5;
		String blosum62 = "ACDEFGHIKLMNPQRSTVWY";	
		int[][] blosumMatrix = 
			 Utils.readMatrixInt("C:\\Users\\josemfer\\Downloads\\BLOSUM62.txt");
		int n = v.length();
		int m = w.length();
		int s[][] = new int[n+1][m+1];
		this.back = new int[n+1][m+1];		
		int down;
		int right;
		int diag;
		
		for (int i=0;i<=n;i++) {
			s[i][0] = -sigma*i;
			this.back[i][0] = 2; // down
		}
		for (int j=1;j<=m;j++) {
			s[0][j] = -sigma*j;
			this.back[0][j] = 0; // right
		}
		for (int i=1;i<=n;i++) {			
			for (int j=1;j<=m;j++) {
				// calculate down and right
				down =  s[i-1][j] - sigma;
				right = s[i][j-1] - sigma;
				// calculate diag				
				char vi = v.charAt(i-1);
				char wj = w.charAt(j-1);				
				diag =  s[i-1][j-1] + blosumMatrix[blosum62.indexOf(vi)][blosum62.indexOf(wj)];
				//save score and backtrack matrix
				
				/* if (i==8 && j==6) {
					System.out.println("down=" + down + "  right="   +right + "diag=" +  diag);
				} */
				
				/*
				if ((diag > right) &&  (diag > down)) {
					s[i][j] = diag;
					back[i][j] = 2;
				} else if ((right > down) &&  (right > diag) ) {
					s[i][j] = right;
					back[i][j] = 1;
				} else {
					s[i][j] = down;
					back[i][j] = 0;
				} 
				*/
				
				s[i][j] = Utils.max(new Integer[]{right,diag, down});			 
				back[i][j] = Utils.maxIndex(new Integer[]{right,diag, down});  
				
				
				
			}				
		}
		return s;
	}
}
